package com.wfm.niuke;

import org.junit.Test;

/**
 * 【买卖股票的最佳时期】
 * 其实做过接雨水这题就很好做
 * 就是找到当前点最右高的点-当前点
 * 然后取最大
 *
 */
public class MaxProfit121 {
    public int maxProfit(int[] prices) {
        int[] max_right = new int[prices.length];
        max_right[prices.length-1]=0;
        for (int i = prices.length-2; i >=0 ; i--) {
            max_right[i] = Math.max(max_right[i+1],prices[i+1]);
        }
        int max = 0;
        for (int i = 0; i < prices.length; i++) {
            if(prices[i]<max_right[i]){
                max = Math.max(max,max_right[i]-prices[i]);
            }
        }
        return max;
    }

    @Test
    public void test121(){
        System.out.println(maxProfit(new int[]{7, 1, 5, 3, 6, 4}));
        System.out.println(maxProfit(new int[]{7, 6,4,3,1}));
    }
}
